home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 20 / Cream of the Crop 20 (Terry Blount) (1996).iso / math / alged34.zip / ALGEDSRC.ZIP / ALGSORT.C < prev    next >
C/C++ Source or Header  |  1996-06-06  |  4KB  |  135 lines
  1. /*--------------------------------------------------------------------
  2.    Alged:  Algebra Editor    henckel@vnet.ibm.com
  3.  
  4.    Copyright (c) 1994 John Henckel
  5.    Permission to use, copy, modify, distribute and sell this software
  6.    and its documentation for any purpose is hereby granted without fee,
  7.    provided that the above copyright notice appear in all copies.
  8. */
  9. #include "alged.h"
  10. /*-----------------------------------------------------------------
  11.    compare two nodes, if they are equal return 1, else 0.
  12. */
  13. int equal(node *p,node *q) {
  14.   int i;
  15.  
  16.   if (p->kind != q->kind) return 0;
  17.   if (p->nump != q->nump) return 0;
  18.   if (p->kind==NUM) return p->value==q->value;
  19.   if (p->kind==VAR) return !strcmp(p->name,q->name);
  20.   if (p->kind==FUN && strcmp(p->name,q->name)) return 0;
  21.  
  22.   for (i=0; i<p->nump; ++i)
  23.     if (!equal(p->parm[i],q->parm[i])) return 0;
  24.  
  25.   return 1;             /* identical */
  26. }
  27.  
  28. /*-----------------------------------------------------------------
  29.    compare two nodes, return -1 if p<q ,0 if p==q ,1 if p>q.
  30.      1. anything < NUM
  31.      2. x < y
  32.      3. x^3 < x^2 < x < y^3
  33.    note: 3 < 2
  34.    other operators have same order as left operand.
  35.    Historical note... this function WAS used for both sorting and
  36.    testing for equality.  However, for maintenance and efficiency
  37.    reasons I found it better to make a separate "equal" function.
  38. */
  39. int cmp(node *p,node *q) {
  40.   int r,i,j,k;
  41.  
  42.   if (p->kind==NUM)                 /* NUMERIC */
  43.     if (q->kind==NUM)
  44.       return p->value==q->value ? 0 :
  45.              p->value < q->value ? 1 : -1;       /* hi to low */
  46.     else return 1;
  47.   else if (q->kind==NUM)
  48.     return -1;
  49.   j = (p->kind==MUL && p->rt->kind==NUM);
  50.   k = (q->kind==MUL && q->rt->kind==NUM);
  51.   if (j && !k) {
  52.     r = cmp(p->lf,q);              /* IGNORE COEFFICIENTS */
  53.     if (r) return r;
  54.     return 1;
  55.   }
  56.   if (k && !j) {
  57.     r = cmp(p,q->lf);
  58.     if (r) return r;
  59.     return -1;
  60.   }
  61.   if (p->kind==VAR) {                 /*  VARIABLES  */
  62.     if (q->kind==VAR)
  63.       return strcmp(p->name,q->name);
  64.     else if (q->nump) {
  65.       r = cmp(p,q->lf);
  66.       if (r) return r;
  67.     }
  68.     return 1;
  69.   }
  70.   else if (q->kind==VAR) {
  71.     if (p->nump) {
  72.       r = cmp(p->lf,q);
  73.       if (r) return r;
  74.     }
  75.     return -1;
  76.   }
  77.   if (p->kind==FUN && q->kind==FUN) {  /* FUNCTIONS */
  78.     r = strcmp(p->name,q->name);
  79.     if (r) return r;
  80.   }
  81.   k = q->kind-p->kind;
  82.   if (!k) k=p->nump-q->nump;
  83.  
  84.   if (!k) {                         /* ARE THEY IDENTICAL? */
  85.     for (i=0; i<p->nump; ++i) {
  86.       r = cmp(p->parm[i],q->parm[i]);
  87.       if (r) return r;
  88.     }
  89.     return 0;             /* identical */
  90.   }
  91.   if (p->nump && q->nump) {           /* DIFFERENT OPERATORS  */
  92.     if (k>0) r = cmp(p->lf,q);
  93.     else     r = cmp(p,q->lf);
  94.     if (r) return r;
  95.   }
  96.   return k;
  97. }
  98.  
  99.  
  100. /*-----------------------------------------------------------------
  101.    sort over operator.  oper = ADD or MUL.
  102.    This uses bubble sort.  It assumes that the nodes have been
  103.    adjusted to left association.  For best results, call bisect
  104.    before calling this.
  105. */
  106. int sortnode(node *p,int oper) {
  107.   int i,r=0;
  108.   node *s,**t;
  109.  
  110.   if (p->kind!=oper) {
  111.     for (i=0; i<p->nump; ++i)
  112.       r+=sortnode(p->parm[i],oper);
  113.     return r;
  114.   }
  115.   while (p->kind==oper) {
  116.     s=p;
  117.     t=p->parm+1;
  118.     while (s->lf->kind==oper) {
  119.       s = s->lf;
  120.       if (cmp(s->rt,*t)>0) t=s->parm+1;
  121.     }
  122.     if (cmp(s->lf,*t)>0) t=s->parm;
  123.     if (*t != p->rt) {             /* too much indirection? */
  124.       s = *t;
  125.       *t = p->rt;
  126.       p->rt = s;
  127.       ++r;
  128.     }
  129.     r+=sortnode(p->rt,oper);
  130.     p = p->lf;
  131.   }
  132.   r+=sortnode(p,oper);
  133.   return r;
  134. }
  135.